package j2025.j01;

import java.util.LinkedList;
import java.util.Queue;

public class j0101 {
    /**
     * 994. 腐烂的橘子
     * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
     *
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
     *
     * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};
        Queue<int[]> q = new LinkedList<>();
        int m = grid.length, n = grid[0].length;
        int count = 0;//好橘子个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 1){
                    count++;
                }else if(grid[i][j] == 2){
                    q.add(new int[]{i,j});
                }
            }
        }
        int ret = 0;
        while(count>0 && !q.isEmpty()){
            int si = q.size();
            for (int a = 0; a < si; a++) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == 1){
                        grid[x][y] = 2;
                        count--;
                        q.add(new int[]{x,y});
                    }
                }
            }
            ret++;
        }
        if(count == 0){
            return ret;
        }else {
            return -1;
        }
    }


}
